1. Field of the Invention
The present invention relates to an image matching device, an image matching method and an image matching program product. In particular, the present invention relates to an image matching device, an image matching method and an image matching program product for matching two images with each other.
2. Description of the Background Art
Several methods of matching fingerprint images have been proposed.
Japanese Patent Laying-Open No. 2003-323618, for example, discloses an image matching device employing the matching method described below. Specifically, in the image matching device disclosed in this publication, a fingerprint image to be matched is divided into a plurality of partial regions, and all the sensing regions are searched to seek a position in a template image where similarity with each of the partial regions is highest. Based on the distribution of the moving vector between a sensing image and a template image highest in match, it is determined whether a particular fingerprint image is identical to the fingerprint on the template image.
Specifically, in the image matching device disclosed in the patent publication cited above, a plurality of partial regions are set in one of two images to be matched, and the other image is searched for a partial region of maximum similarity as a position of maximum similarity.
Currently, the use and ownership of commercial products based on the biometric personal authentication technologies including fingerprint matching are extending. Further, the personal authentication technologies have come to be widely used for such commercial products as portable terminals including mobile phones and PDAs (Personal Digital Assistants) carried by individual persons.
In the personal authentication technologies, the shortening the processing time is crucial. Especially during the spread of the personal authentication technologies, a shorter processing time is an indispensable factor to gain an advantageous position in business competition. Specifically, in an application of the personal authentication technologies to the portable terminals lacking a sufficiently large battery capacity, the reduction in power consumption as well as the shortening the time required for the matching process is a crucial problem.
In the conventional personal authentication technologies employing the matching method as disclosed in the aforementioned patent publication, however, one of the images is divided into a plurality of partial regions and the position of maximum similarity is searched for all the partial regions to search for a data. Therefore, the problem is posed that an excessively large processing time and power are consumed.
With reference to FIGS. 7 to 10C, the processing amount required of the data search method according to the prior art is described. FIG. 7 is a diagram showing a specific example of an image A to be matched. The process executed to match this image A with an image B is described.
First, as shown in FIG. 7, image A to be matched is divided into partial regions R1 to R64 each having a width of 16 and a height of 16, and the partial regions R1 to R64 are matched in that order.
FIGS. 8A to 8C are diagrams for specifically describing the process of searching for the position of maximum similarity in image B with which the partial region R1 of image A has the highest match.
As shown in FIGS. 8A to 8C, a partial region corresponding to partial region R1 of image A is set at the coordinate (1, 1) of image B in a coordinate system with the upper left corner of image B as an origin (FIG. 8A), and the position of maximum similarity is searched for the particular partial region. Next, the partial region of image B corresponding to partial region R1 of image A is moved by one pixel in an x direction (FIG. 8B) and the position of maximum similarity is searched for the particular partial region. Subsequently, the partial region of image B corresponding to partial region R1 is moved pixel by pixel in the x direction to search for the position of maximum similarity for the particular partial region. Once the partial region of image B corresponding to partial region R1 of image A reaches the right end of image B, the same partial region is moved by one pixel in a y direction. In similar fashion, the partial region is moved pixel by pixel in the x direction from the left end to the right end of image B and the position of maximum similarity is searched for the particular partial regions. Finally, the partial regions corresponding to partial region R1 of image A are set to the lower right corner of image B as shown in FIG. 8C. In this way, the position of maximum similarity is searched for all the partial regions of image B corresponding to the partial region R1 of image A.
In similar fashion, a partial region corresponding to partial region R2 of image A is set at the coordinate (1, 1) of image B (FIG. 9A), and the position of maximum similarity is searched for the particular partial region. Next, the partial region of image B corresponding to partial region R2 of image A is moved by one pixel in the x direction (FIG. 9B), and the position of maximum similarity is searched for the particular partial region. Subsequently, the partial region of image B corresponding to partial region R2 of image A is moved pixel by pixel in the x direction to search for the position of maximum similarity. After reaching the right end of image B, the partial region is moved by one pixel in the y direction, and again moved in the x direction pixel by pixel from the left end to the right end of image B to search for the position of maximum similarity. Finally, the partial regions corresponding to partial region R2 of image A are set until the partial region of image B corresponding to partial region R2 of image A reaches the lower right corner of image B, as shown in FIG. 9C. In this way, the position of maximum similarity is searched for each of all the partial regions of image B corresponding to partial region R2 of image A.
A similar process is executed sequentially for partial regions R1 to R64 of image A. Specifically, after the search is repeated up to partial region R63, the partial region corresponding to partial region R64 of image A is set at the coordinate (1, 1) of image B (FIG. 10A), and the position of maximum similarity is searched for the particular partial region. Then, the particular region of image B corresponding to partial region R64 of image A is moved by one pixel in the x direction (FIG. 10B), and the position of maximum similarity is searched for the particular region. After that, the partial region of image B corresponding to partial region R64 of image A is moved pixel by pixel in the x direction to search for the position of maximum similarity. Once the right end of image B is reached, the partial region is moved by one pixel in the y direction and then moved pixel by pixel again in the x direction from left end to right end of image B to search for the position of maximum similarity. Finally, as shown in FIG. 10C, the partial regions corresponding to partial region R64 of image A are set until the lower right corner of image B is reached. In this way, the position of maximum similarity is searched for each of all the partial regions of image B corresponding to partial regions R1 to R64 of image A.
In the process described above, the total number of searches is given as follows.Total number of searches=(number of the partial regions of image B searched for one partial region of image A)×(number of partial regions of image A)
In the case under consideration, the number of the partial regions of image B searched for one partial region of image A is 12769, and the number of the partial regions of image A is 64. Thus, the total number of searches is given as 12769×64=817,216.
As understood from this, the conventional matching method poses the problem that the total number of searches, i.e., the search amount is excessively large and so is the required processing amount, resulting in an excessively large consumption of both the processing time and power.